#include<iostream>
#include<vector>
using namespace std;

// 数组长度、和
int n=4, t=8;

// 存放所有整数
vector<int> a={3, 1, 5, 2};

// 累计解个数
int cnt = 0;

// 输出一个解
void disp(vector<int> &x)
{
	printf("  第%d个解  ", ++cnt);
	printf("选取的数为");
	for (int i=0; i<n; i++)
		if (x[i]==1)
			printf("%d ", a[i]);
	printf("\n");
}

// 递归算法
void dfs(int cs, vector<int> &x, int i)
{
	// 到达一个叶子结点
	if (i >= n)
	{
		// 找到一个满足条件的解, 输出
		if (cs == t)
			disp(x);
	}
	
	// 没有到达叶子结点
	else
	{
		// 选取整数a[i]
		x[i] = 1;
		dfs(cs+a[i], x, i+1);
		
		// 不选取整数a[i]
		x[i] = 0;
		dfs(cs, x, i+1);
	}
}

// 求解子集和问题
void subs1()
{
	// 解向量
	vector<int> x(n);
	
	// i从0开始
	dfs(0, x, 0);
}

int main()
{
	printf("子集和问题解\n"); 
	subs1();
	return 0;
}
